googologywikiaorg-20200223-history
Buchholz hydra
The Buchholz hydra game is a one-player game played on trees labelled with any finite number or \(\omega\). From the game arises a function \(\text{BH}(n)\) whose rate of growth is described by the Takeuti-Feferman-Buchholz ordinal — effectively one of the most powerful computable functions ever defined. Rules The game starts with any labelled tree \(T\), such that the root is marked with a special label (call it +) and every child of root has label 0. This tree is called a hydra. At each step, we perform a transformation on the tree with two parameters: a leaf node \(a\) and a nonnegative integer \(n\). We alter the hydra using the following rules: # If \(a\) has label 0, we proceed as in Kirby-Paris' game. Call the node's parent \(b\), and its grandparent \(c\). First we delete \(a\). If \(c\) exists (i.e. \(b\) is not the root), we make \(n\) copies of \(b\) and all its children and attach them to \(c\). # If \(a\) has label \(u + 1\), we go down the tree looking for a node \(b\) with label \(v \leq u\) (which is guaranteed to exist, as nodes directly above root are all 0's). Consider \(b\) and subtree with root at \(b\), and call that subtree \(S\). Create a copy of \(S\), call it \(S'\). Within \(S'\), we relabel \(b\) with \(u\) and relabel \(a\) with \(0\). Back in the original tree, replace \(a\) with \(S'\). # If \(a\) has label \(\omega\), we simply relabel it with \(n + 1\). If \(a\) is the hydra's rightmost leaf, we notate the transformed tree as \(T(n)\). As we go about altering the hydra, we pick leaves and values of \(n\). The sequence of leaves and \(n\)'s is called a strategy. A strategy is a winning strategy if it eventually leaves us with only the root node, and a losing strategy otherwise. Buchholz's results Buchholz showed that there are no losing strategies for any hydra. Call this the hydra theorem. The hydra theorem is unprovable in , but for individual hydra it is. Suppose we make a tree with just one branch with \(x\) nodes, labeled \(+,0,\omega,\omega,...,\omega\). Call such a tree \(R^n\). It cannot be proven in that for all \(x\), there exists \(k\) such that \(R^x(1)(2)(3)...(k)\) is root tree. (The latter expression means taking the tree \(R^x\), then transforming it with \(n = 1\), then \(n = 2\), then \(n = 3\), etc. up to \(n = k\).) \(\text{BH}(n)\) function Define \(\text{BH}(n)\) as the smallest \(k\) such that \(R^n(1)(2)(3)...(k)\) as defined above is root tree. By the hydra theorem this function is well-defined, but its totality cannot be proven in . Its rate of growth is comparable to \(f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(n)\). (\(\psi_0(\varepsilon_{\Omega_\omega + 1})\) here is the Takeuti-Feferman-Buchholz ordinal, which unsurprisingly measures the strength of .) The first two values of the BH function are virtually degenerate: \(\text{BH}(1) = 0\) and \(\text{BH}(2) = 1\). \(\text{BH}(3)\) is very large; the first few steps of the computation are shown to the right in parenthesis notation. The Buchholz hydra is one of the most powerful known computable functions. It surpasses BEAF, Bird's array notation and TREE(n). The ordinal version is believed to outgrow SCG(n). \(\text{BH}(n)\) is a computable function and is thus still less powerful than . Sources and References *''' W. Buchholz, An independence result for (Π11 - CA) + BI, Ann. Pure Appl. Logic 33 (1987) 131-155. '''* M. Hamano, M. Okada, A relationship among Gentzen's Proof-Reduction, Kirby-Paris' Hydra Game and Buchholz's Hydra Game, Math. Logic Quart. 43 (1997) 103-120. *''' M. Hamano, M. Okada, A direct independence proof of Buchholz's Hydra Game on finite labeled trees, Arch. Math. Logic 37 (1998) 67-89. '''* L. Kirby, J. Paris, Accessible independence results for Peano Arithmetic, Bull. Lon. Math. Soc. 14 (1982) 285-293. * J. Ketonen, R. Solovay, Rapidly growing Ramsey functions, Ann. Math. 113 (1981) 267-314. '''* '''G. Takeuti, Proof Theory, 2nd Edition, North-Holland, Amsterdam, 1987. W. Buchholz, "An independence result for " See also Category:Functions Category:Games Category:Combinatorics